package com.kehao.newcoder;

import org.junit.Test;

public class NC96Solution {

    private class ListNode {
        int val;
        ListNode next = null;
    }

    public boolean isPail(ListNode head) {
        ListNode fast = head,slow = head;
        while (fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        slow = reverse(slow);
        fast = head;
        while (slow!=null){
            if (slow.val != fast.val) {
                return false;
            }
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }

    private ListNode reverse(ListNode node) {
        ListNode next = node.next;
        node.next = null;
        ListNode p;
        while (next!=null){
            p = next.next;
            next.next = node;
            node = next;
            next = p;
        }
        return node;
    }

    @Test
    public void test01(){
        int[] arr = new int[]{1,2,2,1};
        ListNode headFather = new ListNode();
        ListNode tail = headFather;
        for (int i : arr) {
            tail.next = new ListNode();
            tail = tail.next;
            tail.val = i;
        }
        System.out.println(isPail(headFather.next));

    }
}
